外心|小步_牛客白月赛21题解

篇首语：本文由编程笔记#小编为大家整理，主要介绍了牛客白月赛21题解相关的知识，希望对你有一定的参考价值。

https://ac.nowcoder.com/acm/contest/3947

目录

• Audio【计算几何 三角形的外心】
• Channels【容斥】
• DDoS【拓扑排序】
• Exams【模拟】
• Fool Problem【规律】
• Game【博弈】
• ”Happy New Year!“
• I love you【DP】
• Jelly【BFS】

求三角型的外心

#include
using namespace std;
int main()

double x1, x2, x3, y1, y2, y3;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
double A1 &＃61; 2 * (x2 - x1),
B1 &＃61; 2 * (y2 - y1),
C1 &＃61; x2 * x2 - x1 * x1 - y1 * y1 &＃43; y2 *y2,
A2 &＃61; 2 * (x3 - x2),
B2 &＃61; 2 * (y3 - y2),
C2 &＃61; x3 * x3 - x2 * x2 - y2 * y2 &＃43; y3 * y3;
double x,y;
x&＃61;((C1*B2)-(C2*B1))/((A1*B2)-(A2*B1));
y&＃61;((A1*C2)-(A2*C1))/((A1*B2)-(A2*B1));
printf("%.3lf %.3lf\\n",x,y);
return 0;


Channels【容斥】

容斥可做&＃xff0c;但是细节方面有点不咋会写。于是考虑[1,n] 我们算的话是很容易的。
故我们考虑将区间[l,r] 移动到 [1,n] 的位置。

#include
using namespace std;
typedef long long int LL;
LL l,r;
int main()

while(cin>>l>>r)

LL temp&＃61;0;
for(LL i&＃61;l;i<&＃61;r;i&＃43;&＃43;)

if(i%60&＃61;&＃61;0) //找到哪个位置可以整除

temp&＃61;i&＃43;1;
break;


LL len&＃61;(temp-l-10);//将前面不是60整一段多余的计算。
LL sum&＃61;max(len,0ll);
r&＃61;r-(temp-1);//将区间移动到了[1,r]
sum&＃43;&＃61;r/60*50;
r&＃61;r%60;
sum&＃43;&＃61;min(r,50ll);
cout<<sum<<&＃39;\\n&＃39;;

return 0;


DDoS【拓扑排序】

#include
using namespace std;
typedef long long int LL;
const int N&＃61;1e5*3&＃43;10;
const int mod&＃61;20010905;
int h[N],e[N],w[N],ne[N],idx;
LL n,m,d[N],cnt[N];
void add(int a,int b,int c)

e[idx]&＃61;b,w[idx]&＃61;c,ne[idx]&＃61;h[a],h[a]&＃61;idx&＃43;&＃43;;

int main(void)

cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)

int a,b,c; cin>>a>>b>>c;
add(a,b,c);
d[b]&＃43;&＃43;;

queue<int>q; q.push(1);
cnt[1]&＃61;1;
while(q.size())

int u&＃61;q.front(); q.pop();
for(int i&＃61;h[u];i!&＃61;-1;i&＃61;ne[i])

int j&＃61;e[i];
if(--d[j]&＃61;&＃61;0) q.push(j);
cnt[j]&＃61;(cnt[j]&＃43;cnt[u])%mod;


cout<<cnt[n];
return 0;


Exams【模拟】

#include
using namespace std;
const int N&＃61;1e5&＃43;10;
struct node

int op;
double a;
double x1,y1;
double x2,y2;
double x3,y3;
int sum;
Node[N];
int n;
double sum,ans;
int main(void)

cin>>n;
for(int i&＃61;0;i<n;i&＃43;&＃43;)

cin>>Node[i].op>>Node[i].a;
cin>>Node[i].x1>>Node[i].y1;
cin>>Node[i].x2>>Node[i].y2;
cin>>Node[i].x3>>Node[i].y3;
if(Node[i].op&＃61;&＃61;2) continue;
sum&＃43;&＃61;Node[i].a;
Node[i].sum&＃61;Node[i].x1*Node[i].y1&＃43;Node[i].x2*Node[i].y2&＃43;Node[i].x3*Node[i].y3&＃43;0.5;

for(int i&＃61;0;i<n;i&＃43;&＃43;)

if(Node[i].op&＃61;&＃61;2) continue;
ans&＃43;&＃61;Node[i].a/sum*Node[i].sum;

printf("%.2lf",ans);
return 0;


Fool Problem【规律】

#include
using namespace std;
typedef long long int LL;
int main()

string s; cin>>s;
if(s[s.size()-1]%2&＃61;&＃61;0) puts("1");
else puts("-1");
return 0;


Game【博弈】

就是看其分解质数的个数。

#include
using namespace std;
typedef long long int LL;
int cnt&＃61;0;
int main(void)

LL n; cin>>n;
if(n&＃61;&＃61;1)

puts("Nancy");
return 0;

for(int i&＃61;2;i<&＃61;n/i;i&＃43;&＃43;)

while(n%i&＃61;&＃61;0) n/&＃61;i,cnt&＃43;&＃43;;

if(n!&＃61;1) cnt&＃43;&＃43;;
cnt--;//减1就是操作的次数
if(cnt&1) puts("Johnson");
else puts("Nancy");
return 0;


”Happy New Year!“

#include
using namespace std;
typedef long long int LL;
int main(void)

puts("Happy New Year!");
return 0;


I love you【DP】

#include
using namespace std;
typedef long long int LL;
const int N&＃61;15;
const int mod&＃61;20010905;
string a&＃61;".iloveyou";
LL f[15];
int main(void)

string s; cin>>s;
for(int i&＃61;0;i<s.size();i&＃43;&＃43;) s[i]&＃61;tolower(s[i]);
f[0]&＃61;1;
for(int i&＃61;0;i<s.size();i&＃43;&＃43;)

for(int j&＃61;1;j<&＃61;8;j&＃43;&＃43;)
if(s[i]&＃61;&＃61;a[j]) f[j]&＃61;(f[j]&＃43;f[j-1])%mod;

cout<<f[8];
return 0;


Jelly【BFS】

bfs求最小步数。

#include
using namespace std;
const int N&＃61;110;
char a[N][N][N];
int n,st[N][N][N],cnt&＃61;1,flag;
int dx[6]&＃61;-1,0,0,1,0,0;
int dy[6]&＃61;0,-1,1,0,0,0;
int dz[6]&＃61;0,0,0,0,-1,1;
int dist[N][N][N];
struct nodeint z,x,y;;
void bfs()

queue<node>q; q.push(1,1,1);
st[1][1][1]&＃61;1;
memset(dist,-1,sizeof dist);
dist[1][1][1]&＃61;1;
while(q.size())

auto temp&＃61;q.front(); q.pop();
int x&＃61;temp.x,y&＃61;temp.y,z&＃61;temp.z;
for(int i&＃61;0;i<6;i&＃43;&＃43;)

int tempx&＃61;x&＃43;dx[i],tempy&＃61;y&＃43;dy[i],tempz&＃61;z&＃43;dz[i];
if(tempx<&＃61;0||tempx>n||tempy<&＃61;0||tempy>n||tempz<&＃61;0||tempz>n) continue;
if(a[tempz][tempx][tempy]&＃61;&＃61;&＃39;*&＃39;) continue;
if(st[tempz][tempx][tempy]) continue;
cnt&＃43;&＃43;,st[tempz][tempx][tempy]&＃61;1,dist[tempz][tempx][tempy]&＃61;dist[z][x][y]&＃43;1;
q.push(tempz,tempx,tempy);



int main(void)

cin>>n;
for(int k&＃61;1;k<&＃61;n;k&＃43;&＃43;)
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;)
cin>>a[k][i][j];
bfs();
cout<<dist[n][n][n];
return 0;